/*
 * This file is part of Space Invaders: Rehash
 * Copyright (C)2007 Vicent Marti (tanoku@gmail.com)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include <stdio.h>
#include <math.h>

// FIXME: why the fuck do i have one million here? we are playing up to 1000
// ...which means I only have to calc up to sqrt(1000)... which is 100...
// which is slightly less than 1000000...
#define MAX_PRIMES 1000000
bool g_Primes[MAX_PRIMES]; 

// hmmm... this comes straight from the pseudo-code in the Wikipedia entry...
// do some testing maybe? trust my crazy code-translation skills?
void genEratosthenes()
{
	int limit = (int)sqrt((float)MAX_PRIMES);
	
	for ( int i=0; i<MAX_PRIMES; ++i )
		g_Primes[i] = true;
	
	for ( int i=2; i<limit; ++i )
		if ( g_Primes[i] )
			for ( int k=i*i; k<MAX_PRIMES; k+=i )
				g_Primes[k] = false;
}

// talk about efficience ^^
bool isPrime( int n )
{
	return g_Primes[n];
}

int getPrimeN( int n )
{
	int count = 0;
	for ( int i=0; i<MAX_PRIMES; ++i )
	{
		if ( g_Primes[i] )
		{
			count++;
			if ( count == n )
			return i;
		}
	}
	
	return 0;
}
